/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2023-12-12
 * Time:14:24
 */

/**
 * LCR 102. 目标和
 * 给定一个正整数数组 nums 和一个整数 target 。
 * 向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
 *     例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
 * 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
 * 示例 1：
 * 输入：nums = [1,1,1,1,1], target = 3
 * 输出：5
 * 解释：一共有 5 种方法让最终目标和为 3 。
 * -1 + 1 + 1 + 1 + 1 = 3
 * +1 - 1 + 1 + 1 + 1 = 3
 * +1 + 1 - 1 + 1 + 1 = 3
 * +1 + 1 + 1 - 1 + 1 = 3
 * +1 + 1 + 1 + 1 - 1 = 3
 */
public class findTargetSumWays {
    public static void main(String[] args) {
        findTargetSumWays(new int[]{1,1,1,1,1},3);
    }
    static int count;
    static int target;
    public static int findTargetSumWays(int[] nums, int _target) {
        target = _target;
        dfs(nums,0,0);
        return count;
    }

//    private static void dfs(int[] nums, int pos) {
//        if (pos == nums.length){
//            if (sum == target) count++;
//
//            return;
//        }
//        // 加法
//        sum += nums[pos];
//        dfs(nums,pos + 1);
//        sum -= nums[pos];
//        // 减法
//        sum -= nums[pos];
//        dfs(nums,pos + 1);
//        sum += nums[pos];
//    }
    private static void dfs(int[] nums, int pos, int sum) {
        if (pos == nums.length){
            if (sum == target) {
                count++;
            }
            return;
        }
        // 加法
        dfs(nums,pos + 1, sum + nums[pos]);
        // 减法
        dfs(nums,pos + 1, sum - nums[pos]);
    }
}
